#include <bits/stdc++.h>

using namespace std;

int binarySearch(vector<int> &nums, int target)
{
    // write your code here
    int start = 0, end = nums.size() - 1, mid;
    mid = (start + end) / 2;
    while(mid > 0)
    {
        if(nums[mid] == target)
            break;
        else if(nums[mid] < target)
            start = mid;
        else
            end = mid;
        if(mid == (start + end) / 2){
            return -1;
            break;
        }
        mid = (start + end) / 2;
    }
    if(mid == 0)
    {
        if(nums[mid] == target)
            return mid;
        else
            return -1;
    }
    else
    {
        while(mid > 0)
        {
            if(nums[--mid] != target)
                return ++mid;
        }
    }
}

int main()
{
    vector<int> nums = {4,5,9,9,12,13,14,15,15,18};
    int target = 10;
    printf("%d", binarySearch(nums, target));
    return 0;
}
